package com.gitee.swsk33.algorithms.graph.admatrix;

import lombok.Getter;

import java.util.*;

/**
 * 图-邻接矩阵
 * 矩阵存放0或者1，若为无向图，则邻接矩阵对称
 */
public class ADMatrixGraph<T> {

	/**
	 * 顶点集合
	 */
	private T[] vertexes;

	/**
	 * 邻接矩阵
	 */
	private int[][] matrix;

	/**
	 * 是否是有向图
	 */
	private boolean directed;

	/**
	 * 顶点数
	 */
	@Getter
	private int vertexCount;

	/**
	 * 弧的数量
	 */
	@Getter
	private int arcCount;

	/**
	 * 图-邻接矩阵构造函数
	 *
	 * @param vertexes 传入顶点数组以初始化图
	 * @param directed 定义这个图是否是有向图
	 */
	public ADMatrixGraph(T[] vertexes, boolean directed) {
		this.vertexes = vertexes;
		this.directed = directed;
		vertexCount = vertexes.length;
		arcCount = 0;
		// 初始化邻接矩阵，默认都为0
		matrix = new int[vertexCount][vertexCount];
		for (int[] line : matrix) {
			Arrays.fill(line, 0);
		}
	}

	/**
	 * 获取一个顶点在图中顶点列表的下标
	 *
	 * @param vertex 传入一个顶点值
	 * @return 这个顶点在图中顶点列表的下标，若该顶点不存在返回-1
	 */
	public int getVertexIndex(T vertex) {
		for (int i = 0; i < vertexCount; i++) {
			if (vertex == vertexes[i]) {
				return i;
			}
		}
		return -1;
	}

	/**
	 * 获取一个顶点值
	 *
	 * @param index 顶点在图中的下标
	 * @return 对应顶点值
	 */
	public T getVertex(int index) {
		return vertexes[index];
	}

	/**
	 * 设定一个顶点的值
	 *
	 * @param index 要设定顶点的下标
	 * @param value 要设定的值
	 */
	public void setVertex(int index, T value) {
		vertexes[index] = value;
	}

	/**
	 * 添加一个弧
	 *
	 * @param indexStart 弧的起点的下标
	 * @param indexEnd   弧的终点的下标
	 */
	public void addArc(int indexStart, int indexEnd) {
		matrix[indexStart][indexEnd] = 1;
		if (!directed) {
			matrix[indexEnd][indexStart] = 1;
		}
		arcCount++;
	}

	/**
	 * 删除一个弧
	 *
	 * @param indexStart 弧的起点的下标
	 * @param indexEnd   弧的终点的下标
	 */
	public void deleteArc(int indexStart, int indexEnd) {
		matrix[indexStart][indexEnd] = 0;
		if (!directed) {
			matrix[indexEnd][indexStart] = 0;
		}
		arcCount--;
	}

	/**
	 * 两个顶点是否连通
	 *
	 * @param indexStart 起点顶点下标
	 * @param indexEnd   终点顶点下标
	 * @return 起点和终点是否连通
	 */
	public boolean isConnect(int indexStart, int indexEnd) {
		return matrix[indexStart][indexEnd] == 1;
	}

	/**
	 * 获取visit数组中第一个没有被访问的值
	 *
	 * @param visit visit访问数组
	 * @return 第一个没有被访问的值的下标，若全都被访问了则返回-1
	 */
	private int getIndexOfNotVisited(boolean[] visit) {
		for (int i = 0; i < visit.length; i++) {
			if (!visit[i]) {
				return i;
			}
		}
		return -1;
	}

	/**
	 * 深度优先遍历-递归部分
	 *
	 * @param visited 访问数组，用于记录哪些下标的点被访问过
	 * @param start   开始访问的点索引
	 */
	public void DFS(boolean[] visited, int start) {
		// 先访问这个点并标记为已访问
		visited[start] = true;
		// 这里用输出代替访问操作
		System.out.println(vertexes[start]);
		// 搜寻这个点的邻接点
		for (int i = 0; i < vertexCount; i++) {
			// 找到第一个和其邻接并未访问的点，递归访问
			if (matrix[start][i] != 0 && !visited[i]) {
				DFS(visited, i);
			}
		}
	}

	/**
	 * 深度优先遍历-启动部分
	 */
	public void doDFS() {
		// 初始化visited数组
		boolean[] visited = new boolean[vertexCount];
		Arrays.fill(visited, false);
		// 对没访问过的点执行DFS
		int notVisit;
		while ((notVisit = getIndexOfNotVisited(visited)) != -1) {
			DFS(visited, notVisit);
		}
	}

	/**
	 * 广度优先遍历
	 */
	public void doBFS() {
		// 初始化访问数组
		boolean[] visited = new boolean[vertexCount];
		Arrays.fill(visited, false);
		// 广度优先遍历队列
		Queue<Integer> queue = new LinkedList<>();
		// 执行BFS
		int currentVisit;
		while ((currentVisit = getIndexOfNotVisited(visited)) != -1) {
			// 访问第一个没被访问的点，并入队
			// 以输出代替访问操作
			System.out.println(vertexes[currentVisit]);
			visited[currentVisit] = true;
			queue.offer(currentVisit);
			while (!queue.isEmpty()) {
				// 出队，对其邻接点进行访问
				int currentIndex = queue.poll();
				for (int i = 0; i < vertexCount; i++) {
					// 对于没访问过的邻接点全部访问并加入队列
					if (!visited[i] && matrix[currentIndex][i] != 0) {
						queue.offer(i);
						// 访问
						System.out.println(vertexes[i]);
						visited[i] = true;
					}
				}
			}
		}
	}

	/**
	 * 用于输出
	 */
	@Override
	public String toString() {
		StringBuilder result = new StringBuilder();
		for (int[] line : matrix) {
			for (int value : line) {
				result.append(value).append(" ");
			}
			result.append("\r\n");
		}
		return result.toString();
	}

}